1. Field
Embodiments generally relates to systems and methods for solving the shortest path problem and, more specifically in some embodiments, to a system and method for solving the shortest path problem on a graph with multi-edge constraints in a time and space efficient manner.
2. Description of Related Art
The shortest path problem is the problem of finding a path between two nodes of a graph that minimizes the sum of the weights of the path's edges. A real-world example of the shortest path problem is navigating a city's streets. A driver desires to get from one area of the city to another area of the city by driving the quickest route possible. The quickest route is determined by considering how far the driver must drive on each street in the city to get to the destination and how quickly the driver can drive on each of the streets, and then selecting the combination of streets in the city that minimize the amount of traveling time between the starting location and the destination. Depending on traffic, construction, road restrictions, etc., the quickest route can change considerably. In the above example, the city's network of streets is modeled as a graph. The nodes of the graph are the starting location and destination of the driver and all intersections in the street network. The streets the driver could travel on during the trip are the edges of the graph. Each edge is also assigned a weight representing the amount of time the driver must spend traveling the street that corresponds to the edge.
Several techniques have been developed to solve the shortest path problem, but all have considerable limitations. Dijkstra's algorithm can solve the shortest path problem, but only for a graph where the edge weights are independent of all previous edges. For example, continuing our driving example above, Dijkstra's algorithm cannot find the quickest route between two locations in a city where the city's network of streets has driving constraints based on which edge the driver has come from, such as no-left turns at certain intersections. The A* algorithm, which can also solve the shortest path program, is subject to the same limitations. Finally, while a simple breadth-first search with a priority queue can solve the shortest path problem, it is still subject to many of the same limitations. In particular, a breadth-first search will never allow a route where the same intersection must be visited twice. For example, if a left turn at an intersection is not allowed, the fastest route may be to go straight at the intersection, perform three right turns around a city block, and then go straight again at the same intersection.